#include<stdio.h>
#include <stdlib.h>

/*

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：
1 顺序表申请的存储容量；
2 顺序表的长度，也就是表中存储数据元素的个数；

*/

typedef struct table
{
	//声明了一个名为head的长度不确定的数组，也叫“动态数组”
	int *head;
	//记录当前顺序表的长度
	int length;
	//记录顺序表分配的存储容量
	int size;
} Table;


#define Size 5
//初始化顺序表
Table initTable()
{
	Table t;
	t.head = (int*)malloc(Size * sizeof(int));
	if (!t.head)
	{
		printf("initTable初始化失败\n");
		exit(0);
	}
	
	t.length = 0;
	t.size = Size;
	
	return t;
}
//输出顺序表中的元素
void displayTable(Table t)
{
	for (int i = 0; i < t.length; i++)
	{
		printf("%x %d   ", (t.head + i), *(t.head + i));
	}
	printf("\n");
	printf("顺序表大小：%d \n", t.size);
	printf("顺序表长度：%d \n", t.length);
	printf("\n");
}

//释放内存
void destroyTable(Table t)
{
	free(t.head);
	t.head = NULL;
	t.length = 0;
	t.size = 0;
}

/*
顺序表插入元素
根据插入位置不同，存在 3 种情况：
1 插入到顺序表表头
2 在表的中间位置插入元素
3 最后一个位置插入元素

[1][2][3][4][5]
       |
       目标位置
	   
[1][2][ ][3][4][5]
       | (整体后移)
       目标位置	   
	   
[1][2][6][3][4][5]
*/

/*
	t 待插入的顺序表
	elem 待插入的元素
	add 插入的指定位置
*/
Table addTable(Table t, int elem, int add)
{
	//判断插入位置是否合法
	if (add > t.length || add < 0) 
	{
		printf("插入位置非法\n");
		return t;
	}
	//判断内存是否足够
	if (t.length == t.size) 
	{
		//重新调整 malloc 分配的内存空间
		t.head = (int*) realloc(t.head, (t.size + 1)*sizeof(int));
		
		if (!t.head) 
		{
			printf("addTable 存储分配失败\n");
			return t;
		}
		
		t.size += 1;
	}
	
	/*
	插入操作，将插入位置的元素逐个后移 (1 2 3 4 5) 
	4; 4 > 2; 4--	n 移向 n + 1
	3; 3 > 2; 4--   n - 1 移向 n 
	
	*/
	for (int i = t.length - 1; i >= add; i--) 
	{
		t.head[i + 1] = t.head[i];
	}
	//后移完成插入元素
	*(t.head + add) = elem;
	t.length++;
	return t;
}

/*
顺序表删除元素
删除指定位置元素，其后元素整体前移 1 个位置（整体前移覆盖可间接实现删除目的）

-----[1][2][3][4][5]------
-----[1][2][4][5]------

*/
/**
	t --- 需要删除的顺序表
	add --- 删除的位置

*/
Table delTable(Table t, int add)
{
	//校验删除位置是否合法
	if (add < 0 || add > t.length - 1) 
	{
		printf("delTable -> 要删除的目标元素位置非法\n");
		return t;
	}
	
	//删除操作
	for (int i = add + 1; i < t.length; i++) 
	{
		t.head[i - 1] = t.head[i];
	}
	
	
	t.length--;
	return t;
}

int main()
{
	
	Table t = initTable();
	
	for (int i = 0; i < Size; i++)
	{
		*(t.head + i) = i + 1;
		t.length++;
	}
	
	printf("顺序表中存储的元素分别是：\n");
	displayTable(t);
	
	printf("中间位置插入元素\n");
	t = addTable(t, 88, 2);
	displayTable(t);
	
	printf("末尾插入元素\n");
	t = addTable(t, 88, t.length);
	displayTable(t);
	
	printf("头插入元素\n");
	t = addTable(t, 88, 0);
	displayTable(t);
	
	printf("删除第 2 个元素（下标从 0 开始）\n");
	t = delTable(t, 2);
	displayTable(t);
	
	//释放内存
	destroyTable(t);
    return 0;
}